package j2024.j202407;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class ListNode1 {
   int val;
   ListNode next = null;
   public ListNode1(int val) {
     this.val = val;
   }
 }
public class j0720 {
    public static void main1(String[] args) {
        Thread t =new Thread();
    }
    public String solve1 (String s, String t) {
        // write code here
        if(s.equals("0") || t.equals("0")){
            return "0";
        }
        int[] ret = new int[s.length()+t.length()];
        for (int i = s.length()-1; i >=0; i--) {
            for (int j = t.length()-1; j >=0 ; j--) {
                ret[i+j+1] += (s.charAt(i)-'0')*(t.charAt(i)-'0');
            }
        }
        int end = s.length()+t.length()-1;
        while(end>0){
            ret[end-1]+=ret[end]/10;
            ret[end]%=10;
            end--;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < ret.length; i++) {
            if(i==0 && ret[i]==0){
                continue;
            }
            sb.append((char) (ret[i]+'0'));
        }
        return sb.toString();
    }
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        if(head1 == null){
            return head2;
        }
        if(head2 == null){
            return head1;
        }
        head1 = reverse(head1);
        head2 = reverse(head2);
        int num = 0;
        ListNode newhead = new ListNode(-1);
        ListNode n = newhead;
        while(head1!=null || head2!=null||num!=0){
            if(head1!=null){
                num+=head1.val;
                head1 = head1.next;
            }
            if(head2!=null){
                num+=head2.val;
                head2 = head2.next;
            }
            n.next =  new ListNode(num%10);
            n = n.next;
            num/=10;
        }
        newhead = reverse(newhead);
        return newhead.next;
    }

    private ListNode reverse(ListNode head) {
        if(head == null){
            return head;
        }
        ListNode prev = null;
        ListNode cur = head;
        while(cur!=null){
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

    public String solve2 (String s, String t) {
        // write code here
        Stack<Integer> stack = new Stack<>();
        int a = s.length()-1,b = t.length()-1;
        int num = 0;
        while(a>=0 || b>=0 || num!=0){
            if(a>=0){
                num+=s.charAt(a--)-'0';
            }else {
                num+=0;
            }
            if(b>=0){
                num+=t.charAt(b--)-'0';
            }else {
                num+=0;
            }
            stack.push(num%10);
            num/=10;
        }
        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()){
            sb.append(stack.pop());
        }
        return sb.toString();
    }

    public String solve (String ss, String tt) {
        // write code here
        char[] s = new StringBuilder(ss).reverse().toString().toCharArray();
        char[] t = new StringBuilder(tt).reverse().toString().toCharArray();
        int m = s.length,n = t.length;
        int[] ret = new int[m+n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ret[i+j] += (s[i]-'0')*(t[j]-'0');
            }
        }
        StringBuilder sb = new StringBuilder();
        int c = 0;
        for(int x:ret){
            c+=x;
            sb.append((char) (c%10+'0'));
            c/=10;
        }
        while(c!=0){
            sb.append((char) (c%10+'0'));
            c/=10;
        }
        while(sb.length()>1 && sb.charAt(sb.length()-1)=='0'){
            sb.deleteCharAt(sb.length()-1);
        }
        return sb.reverse().toString();
    }
    int[] dx = {0,0,-1,1};
    int[] dy = {1,-1,0,0};
    //1162
    public int maxDistance(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        Queue<int[]> q = new LinkedList<>();
        int[][] dis =  new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dis[i][j] = -1;
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(grid[i][j] == 1){
                    dis[i][j] = 0;
                    q.add(new int[]{i,j});
                }
            }
        }
        int ret = -1;
        while(!q.isEmpty()){
            int[] tmp = q.poll();
            int  a = tmp[0],b = tmp[1];
            for (int i = 0; i < 4; i++) {
                int x = a+dx[i],y = b+dy[i];
                if(x>=0 && x<m && y>=0 && y<n && dis[x][y]==-1){
                    dis[x][y] = dis[a][b]+1;
                    ret = Math.max(ret,dis[x][y]);
                    q.add(new int[]{x,y});
                }
            }
        }
        return ret;
    }
    //1765
    public int[][] highestPeak(int[][] isWater) {
        int m = isWater.length;
        int n = isWater[0].length;
        Queue<int[]> q = new LinkedList<>();
        boolean[][] vis = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(isWater[i][j]==1){
                    q.add(new int[]{i,j});
                    isWater[i][j] = 0;
                    vis[i][j] = true;
                }
            }
        }
        while(!q.isEmpty()){
            int[] tmp = q.poll();
            int a = tmp[0],b = tmp[1];
            for (int i = 0; i < 4; i++) {
                int x = a+dx[i],y = b+dy[i];
                if(x>=0 && x<m && y>=0 && y<n && !vis[x][y] && isWater[x][y] == 0){
                    isWater[x][y] = isWater[a][b]+1;
                    vis[x][y] = true;
                    q.add(new int[]{x,y});
                }
            }
        }
        return isWater;
    }

}
